package com.df.sort;

/**
 * 插入排序，希尔排序
 *
 * @author dongfang
 */
public class Insert {


    /**
     * <EM>插入排序（Insertion Sort）</EM>的算法描述是一种简单直观的排序算法。<BR/>
     * 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。<BR/>
     * 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），
     * 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
     * <p>
     * 步骤：
     * <pre>
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 将新元素插入到该位置中
     * 6. 重复步骤2
     * <pre/>
     *
     * @param array
     */
    public static void insertion(int[] array) {
        int num = 1;
        int length = array.length;
        int temp = 0;

        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0 && (array[j - 1] > array[j]); j--) {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                num++;
                // System.out.println("[" + num++ + "][" + i + "][" + j + "] : " + Arrays.toString(array));
            }
        }
        System.out.println("insertion num [" + num + "]");

    }


    /**
     * <EM>希尔排序</EM>，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
     * <pre>
     * 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
     *      1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
     *      2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
     * </pre>
     * 由于shell排序的时间复杂度和步长有关，目前还没法证明哪个步长效率最好，此处用Knuth提出的方法；<BR/>
     *
     * @param array
     */
    public static void shell(int[] array) {
        int num = 1;
        int length = array.length;
        int temp = 0;

        int h = 0;
        while (h <= length / 3) {
            h = h * 3 + 1;
        }

        while (h > 0) {
            // System.out.println("h = " + h);
            for (int i = h; i < length; i += h) {
                for (int j = i - h; j > -1 && array[j] > array[j + h]; j--) {
                    temp = array[j + h];
                    array[j + h] = array[j];
                    array[j] = temp;
                    num++;
                    // System.out.println("[" + num++ + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                }
            }
            h = (h - 1) / 3;
        }
        System.out.println("shell num [" + num + "]");

        // 当h == 1时, 就变成了直接插入排序了

        // while (1 > 0) {
        //     System.out.println("h = " + 1);
        //     for (int i = 1; i < length; i += 1) {
        //         for (int j = i - 1; j > -1 && array[j] > array[j + 1]; j--) {
        //             temp = array[j + 1];
        //             array[j + 1] = array[j];
        //             array[j] = temp;
        //             System.out.println("[" + num++ + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
        //         }
        //     }
        //     h = (1 - 1) / 3;
        // }

    }

}
